[poj1845]Sumdiv

发表于 | 分类于 ， | | 阅读次数:

题目

题目描述

Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901).

输入

The only line contains the two natural numbers A and B, (0 <= A,B <= 50000000)separated by blanks.

输出

The only line of the output will contain S modulo 9901.

样例输入

1
2 3

样例输出

1
15

提示

$ 2^3 = 8. $
The natural divisors of 8 are: 1,2,4,8. Their sum is 15.
15 modulo 9901 is 15 (that should be output).

来源

Romania OI 2002

传送门

Sumdiv

题解

问题分析

刚一看到这个题，一股浓浓的数论感就扑面而来，求$ A^B $的约数和，暴力当然是不可取的，我们不妨换个角度
如果我们把$ A $分解质因数，表示为

$$ A=p_1^(c_1)p_2^(c_2)p_3^(c_3)…p_n^(c_n) $$

那么$ A^B $可表示为
$$ A=p_1^(Bc_1)p_2^(Bc_2)p_3^(Bc_3)…p_n^(Bc_n) $$
则$ A^B $所有约数和为
$$ (1+p_1+p_1^2+…+p_1^(Bc_1)) $$

质因数分解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define MAXN 50001
const int MOD=9901;
long long a,b;
long long p[MAXN],c[MAXN];
long long m;
long long ans;
 
 
long long pow(long long p,long long n){
    long long sq=1;
    while(n){
        if(n&1)sq=(sq*p)%MOD;
        n>>=1;
        p=(p*p)%MOD;
    }
    return sq;
}
 
bool prime(int n){
    if(n<2)return 0;
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0)return 0;
    }
    return 1;
}
 
void divide(int n){
    m=0;
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0&&prime(i)){
            p[++m]=i,c[m]=0;
            while(n%i==0)n/=i,c[m]++;
        }
    }
    if(n>1&&prime(n))p[++m]=n,c[m]=1;
    return;
}
 
long long sum(long long p,long long c){
    if(c==0)return 1;
    if(c%2==0)return (sum(p,c/2-1)*(1+pow(p,c/2+1))+pow(p,c/2))%MOD;
    else return (sum(p,c/2)*(1+pow(p,c/2+1)))%MOD;
}
 
void work(){
    ans=1;
    for(int i=1;i<=m;i++){
        ans=(ans*sum(p[i],c[i]*b)%MOD)%MOD;
    }
}
 
int main(){
    cin>>a>>b;
    divide(a);
    work();
    printf("%lld",ans);
    return 0;
}